1. Field of the Invention
This invention is related to the field of communication fabric arbiters.
2. Description of the Related Art
Digital systems of various types generally include a variety of components connected together via a communication fabric. The communication fabric can include buses, point-to-point links, hierarchical interconnects, full or partial crossbars, etc. At various points within the fabric, transactions from different sources can share part of the fabric. Generally, an arbiter is employed to select among the transactions when there is a conflict. For example, a conflict can occur when transactions arrive at the shared point contemporaneously. A conflict can occur when sources connected to a shared point (e.g. a shared bus) concurrently have transactions to initiate. Various arbitration schemes exist to perform the transaction selection, typically attempting to be fair over time to each source, to prevent starvation of each source, and to provide high performance and high utilization of the bandwidth on the fabric.
One type of arbitration scheme is a “round robin” scheme. In the round robin scheme, the sources are logically ordered in a ring. The order of sources in the ring is referred to as the round robin order, and does not necessarily correlate to the physical locations of the sources. The arbiter maintains a pointer to one of the sources, and that source is the highest priority source for transactions for the current arbitration. The arbiter can select a transaction from the source that is identified as highest priority, and can advance the pointer to the next source in the round robin order. The pure round robin scheme provides equal opportunity to each source over time, but may not always match up to when the source has a transaction to send. Additionally, providing equal opportunity to all sources may not be the best overall scheme for performance. For example, the sources can have different bandwidth requirements, and thus better overall performance can be achieved by providing more bandwidth to some sources than others.
A mechanism for allocating bandwidth unequally in the round robin scheme is the deficit-weighted round robin scheme. In the deficit-weighted scheme, a weight is assigned to each source that is proportional to the amount of bandwidth that is assigned to that source. Each time a transaction from the source wins arbitration, its weight is updated. Once its weight is consumed, the source is skipped in the round robin arbitration. Once the weights for all sources are exhausted, the weights can be reloaded. In some cases, the weights are also reloaded if all the sources that have transactions to transmit have exhausted their weights, even if a source that has no transactions has not exhausted its weight. However, such a scheme may create issues for sources that are operating more slowly than the fabric itself. Such sources can only transmit a transaction to the arbiter once per clock cycle of their slower clock. Accordingly, at the higher clock frequencies, it can appear that the slower source does not have a transaction to send when it actually does have one. The weights can thus be falsely reloaded, which can result in different bandwidth characteristics than those expected from the configuration of the weights.